# -*- encoding: utf-8 -*-
'''
Filename         :31_nextPermutation.py
Description      :
Time             :2022/08/23 16:49:23
Author           :daiyizheng
Email            :387942239@qq.com
Version          :1.0
'''

from typing import List


class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        ## 解题思路：
        # 1. 从屁股往前找，找到一个 i，满足nums[i] < nums[i+1]
        # 2. 在第i位置后面，从右边往左找，找到第一个比i数字大的位子j
        # 3. 调换 i 与 j的值， 
        # 4. 翻转 i 之后所有的值， 不包括i位子
        # 5  特殊情况 第一步一直不满足 nums[i] < nums[i+1]， 直接翻转整个数组， 例如： 6 5 4 3 2 1 
        i = len(nums)-2
        # step1
        while i>=0 and nums[i]>=nums[i+1]:
            i -= 1
        
        if i>=0:
            # step2
            j = len(nums)-1
            while j>=0 and nums[i]>=nums[j]:
                j -=1
            
            # 交换
            nums[i], nums[j] = nums[j], nums[i]
        
        ## 反转i之后的
        left, right = i+1, len(nums)-1

        while left<right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1
        




if __name__ == '__main__':
    Solution().nextPermutation([1,2,3,4,5,6,7])